import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * 希尔排序算法：插入排序算法的升级版
 * 并测算处理80000个排序，需要花费多少时间?  (交换式)本人电脑：7秒
 * 并测算处理80000个排序，需要花费多少时间?  (移位式)本人电脑：1秒
 */
public class ShellSortDemo {
    public static void main(String[] args) {
//        int[] ints = new int[]{8,9,1,7,2,3,5,4,6,0};
        int[] ints = new int[]{8, 9, 1, 7, 2, -5, 0, 68, -5, -64, 3, 5, 4, 6, 0};
        System.out.println("排序前数组：");
        System.out.println(Arrays.toString(ints));
        shellSort2(ints);
        System.out.println("排序后数组：");
        System.out.println(Arrays.toString(ints));
        System.out.println("----------------------------");

        //测试算法(交换式)：若处理80000个排序，需要花费多少时间? 本人电脑：7秒
        shellSortTest();
        System.out.println("------------------------------");
        //测试算法(交换式)：若处理80000个排序，需要花费多少时间? 本人电脑：1秒
        shellSort2Test();
    }

    //测试算法(交换式)：若处理80000个排序，需要花费多少时间? 本人电脑：7秒
    public static void shellSortTest() {
        int[] arr = new int[80000];
        //先随机生成一个容量为80000个的数组
        for (int i = 0; i < 80000; i++) {
            arr[i] = (int) (Math.random() * 80000);
        }
        //创建 格式化日期格式对象：
        SimpleDateFormat sdf = new SimpleDateFormat("yyyy.MM.dd HH:mm:ss");
        //创建当前时间的对象
        Date time1 = new Date();
        //对当前时间进行格式化
        String s1 = sdf.format(time1);
        //打印
        System.out.println("排序前时间：" + s1);
        //进行排序
        shellSort(arr);
        //再次创建当前时间对象
        Date time2 = new Date();
        String s2 = sdf.format(time2);
        System.out.println("排序后时间：" + s2);
    }

    //希尔排序算法：交换式
    public static void shellSort(int[] arr) {
        //第一轮排序 将10个数据分成10/2=5组
        int temp = 0;   //中间转换变量
        int gaps = arr.length / 2;  //分组数

        //1.确定每次自动分组数量：分组数量 = 数组长度/2^n（n>0,n:表示第几次分组）
        for (int i = gaps; gaps > 0; gaps /= 2) {
            /**
             * 2.每次分组之后，
             *      1）如何确定组内数据是哪些？
             *          从第一个数据开始（包括第一个），数组下标每次加上分组数量的数，直到数组最后没有那个数为止
             *      2）如何分别进行各个组内的排序？
             *       （1. 这个”分别“，不是真正的分别进行，实质上是从数组中找到起始点，依次开始进行相邻两个组内数进行比较，从小到大排序，直到数组最后一个数；
             *       （2. 若某个数的下标是分组数量的倍数，那么这个数就需要进行多次循环比较，有点类似冒泡排序（为什么这样？这是希尔排序算法的核心）
             *       （3. 起始数下标 = 分组数量-1 = 组内两个数据的间距
             */
            for (int j = gaps; j < arr.length; j++) {
                //3.每个分组里面的每一个数，都需要依次进行组内循环比较，
                // 若某个数是分组数的倍数，那么这个数就需要进行多次循环比较，有点类似冒泡排序,相邻两个数比较，前小后大就交换位置
                for (int k = j - gaps; k >= 0; k -= gaps) {
                    //若前面的数比后面的数大，就交换两个数的位置
                    if (arr[k] > arr[k + gaps]) {
                        temp = arr[k];
                        arr[k] = arr[k + gaps];
                        arr[k + gaps] = temp;
                    }
                }
            }
        }
    }

    //测试算法(移位式)：若处理80000个排序，需要花费多少时间? 本人电脑：1秒
    public static void shellSort2Test() {
        int[] arr = new int[80000];
        //先随机生成一个容量为80000个的数组
        for (int i = 0; i < 80000; i++) {
            arr[i] = (int) (Math.random() * 80000);
        }
        //创建 格式化日期格式对象：
        SimpleDateFormat sdf = new SimpleDateFormat("yyyy.MM.dd HH:mm:ss");
        //创建当前时间的对象
        Date time1 = new Date();
        //对当前时间进行格式化
        String s1 = sdf.format(time1);
        //打印
        System.out.println("排序前时间：" + s1);
        //进行排序
        shellSort2(arr);
        //再次创建当前时间对象
        Date time2 = new Date();
        String s2 = sdf.format(time2);
        System.out.println("排序后时间：" + s2);
    }

    //希尔排序算法：移位式(交换式的优化)
    public static void shellSort2(int[] arr) {
        //待插入值索引
        int insertIndex = 0;
        //待插入值
        int insertVal = 0;
        for (int gaps = arr.length / 2; gaps > 0; gaps /= 2) {//分组
            for (int i = gaps; i < arr.length; i++) {//组内循环
                insertIndex = i;        //待插入值的下标
                insertVal = arr[i];     //待插入值
                while (insertIndex - gaps >= 0 && insertVal < arr[insertIndex - gaps]) {
                    arr[insertIndex] = arr[insertIndex - gaps];
                    insertIndex -= gaps;
                }
                if (insertIndex != i) {//若本身待插入值就比前一个值大，就不用赋值了
                    arr[insertIndex] = insertVal;
                }
            }

        }

    }
}